{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Please input the size of population: \n",
      "Please input the size of Crossover Rate: \n",
      "Please input the size of Mutation Rate: \n",
      "Please input the mutation selection rate: \n",
      "Please input number of iteration: \n",
      "optimal sequence [4, 3, 6, 7, 5, 8, 5, 7, 8, 3, 4, 5, 5, 4, 1, 1, 3, 5, 2, 6, 3, 3, 6, 8, 2, 9, 9, 2, 9, 4, 1, 7, 9, 6, 0, 7, 4, 3, 4, 3, 2, 8, 3, 2, 1, 0, 1, 6, 5, 1, 7, 8, 0, 2, 8, 7, 0, 6, 8, 6, 9, 7, 7, 9, 2, 4, 8, 4, 1, 0, 0, 6, 0, 1, 2, 8, 0, 5, 7, 9, 2, 3, 8, 9, 1, 0, 4, 6, 5, 7, 9, 2, 4, 5, 1, 9, 3, 6, 5, 0]\n",
      "optimal value:1165.000000\n",
      "the elapsed time:43.17110729217529\n"
     ]
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAZQAAAEPCAYAAABlZDIgAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMi4yLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvhp/UCwAAHidJREFUeJzt3XuUXGWd7vHvk0QJoIFgooYETHCQM0ERmUyAw6i4UAzogMqcOURc5HiLOGSJZ3SUHBRQls4oxyuiCEMOMsNlnEE0algho2gGR5CgXJVLuEkMQiCQwACJSX7nj/dt2alUddfu3lXVXfv5rFWrq969q+rXu7vr6fd990URgZmZ2UiN63UBZmbWHxwoZmZWCQeKmZlVwoFiZmaVcKCYmVklHChmZlYJB4qZmVXCgWJmZpXoeqBIWiLpEUm3NVn2UUkhaUp+LElflbRa0i2SDiqsu0DS3fm2oJvfg5mZ7WhCD97zIuBrwMXFRkl7AW8CfltoPgrYN98OBr4BHCxpD+AMYA4QwI2SlkbE44O98ZQpU2LmzJnVfBdmZjVw4403PhoRU9tZt+uBEhErJc1ssuhLwMeA7xXajgUujnR+mOsk7S5pGnA4sCIi1gNIWgHMAy4b7L1nzpzJqlWrRvw9mJnVhaQH2l13VMyhSDoG+F1E3NywaDrwYOHxmtzWqr3Zay+UtErSqnXr1lVYtZmZFfU8UCTtApwGnN5scZO2GKR9x8aI8yNiTkTMmTq1rV6bmZkNQ88DBXg5MAu4WdL9wAzgl5JeSup57FVYdwawdpB2MzPrkZ4HSkTcGhEvjoiZETGTFBYHRcTvgaXAiXlvr0OADRHxELAcOFLSZEmTgSNzm5mZ9Ugvdhu+DPg5sJ+kNZLeO8jqy4B7gdXABcDfAOTJ+LOAG/Lt0wMT9GZm1huq0wW25syZE97Ly8ysfZJujIg57azb8yEvMzPrDw6UNpx1Fiz3DI2Z2aB6caT8mHP66bDffnDHHb2uxMxs9HIPpQ3z58PWrb2uwsxsdHOgtEGCGu27YGY2LA6UNowb50AxMxuKA6UNEmzb1usqzMxGNwdKG9xDMTMbmgOlDe6hmJkNzYHSBvdQzMyG5kBpg3soZmZDc6C0wT0UM7OhOVDa4B6KmdnQHCht8IGNZmZDc6C0wUNeZmZDc6C0wUNeZmZDc6C0wT0UM7OhOVDa4B6KmdnQHChtcA/FzGxoDpQ2uIdiZjY0B0obvNuwmdnQHChtGDfOPRQzs6E4UNrgHoqZ2dAcKG3wpLyZ2dAcKG3wpLyZ2dAcKG1wD8XMbGgOlDa4h2JmNjQHShvcQzEzG5oDpQ0DPZR//Ee4775eV2NmNjo5UNqw557p6/vfD4sX97YWM7PRyoHShg98ANauhdmz4Zlnel2Nmdno5EBpgwTTpsHEibB1a6+rMTMbnRwoJUyYAFu29LoKM7PRyYFSwvjx7qGYmbXS1UCRtETSI5JuK7SdJekWSTdJulrSnrn9cEkbcvtNkk4vPGeepDslrZZ0arfqnzDBgWJm1kq3eygXAfMa2s6OiAMi4kDgB8DphWX/EREH5tunASSNB84FjgJmA/Mlze586amH4iEvM7PmuhooEbESWN/QtrHwcFdgqEMI5wKrI+LeiNgMXA4cW2mhLXjIy8ystVExhyLpM5IeBE5g+x7KoZJulnSVpP1z23TgwcI6a3Jbx3lS3systVERKBFxWkTsBVwCLMrNvwReFhGvBs4Bvpvb1ewlWr22pIWSVklatW7duhHV6R6KmVlroyJQCi4FjoM0FBYRT+X7y4DnSZpC6pHsVXjODGBtqxeMiPMjYk5EzJk6deqIipswATZvHtFLmJn1rZ4HiqR9Cw+PAe7I7S+VpHx/LqnWx4AbgH0lzZL0fOB4YGk3at22DW69FTZs6Ma7mZmNLRO6+WaSLgMOB6ZIWgOcARwtaT9gG/AAcFJe/a+AD0raAjwDHB8RAWyRtAhYDowHlkTE7d2of/Zs+MEP4NFHYbfduvGOZmZjR1cDJSLmN2m+sMW6XwO+1mLZMmBZhaW15VWvGnj/br+zmdno1/Mhr7FkXN5avtiWmdmOHCglKO9f5kAxM9uRA6WEgR6Kh7zMzHbkQCnBPRQzs9YcKCW4h2Jm1poDpQRPypuZteZAKWFgyMs9FDOzHTlQSnAPxcysNQdKCZ6UNzNrzYFSgiflzcxac6CU4CEvM7PWHCgleFLezKw1B0oJ7qGYmbXmQCnBPRQzs9YcKCW4h2Jm1poDpQTv5WVm1poDpQQfh2Jm1poDpQQPeZmZteZAKcGT8mZmrTlQSnAPxcysNQdKCZ6UNzNrbUKvCxhLBoa8LrgAfvSjodffc0/40Ic6W5OZ2WjhQClh773hxS+GpUuHXnfLFti6FY4/Pj3HzKzfecirhOnT4eGH4dlnh76de256ztatva3ZzKxbSvVQJD0POAV4BzADmNi4TkT4//ECz7eYWV2UHfL6EvAB4AfANcDmyivqEwPzLWZmdVE2UP4HcGpEfKETxfQTH7NiZnVTdg5FwC2dKKRfOVDMrC7KBsoFwPxOFNJv3EMxs7opO+T1MHCCpGuAFcATDcsjIr5RSWVjnOdQzKxuygbKl/PXvYHXN1kegAMF91DMrH5KBUpE+LiVkhwoZlYXDogO8ZCXmdXNsE69ImkG8AqaH9i4bKRF9QMPeZlZ3ZQ9Uv6FwLeBIwea8tfix+b4CurqGw4UM6uLskNef0+akH8tKUzeDhwOXAjcBxwy1AtIWiLpEUm3FdrOknSLpJskXS1pz9wuSV+VtDovP6jwnAWS7s63BSW/j45zD8XM6qZsoBwNfAa4Pj9eGxErI2Ih8D3g79p4jYuAeQ1tZ0fEARFxIOm0Lqfn9qOAffNtIXkPMkl7AGcABwNzgTMkTS75vXSU51DMrG7KBspLgAcjYivwX8AehWXLeG4orKWIWAmsb2jbWHi4K88NoR0LXBzJdcDukqYBbwZWRMT6iHicdExMY0j1lHsoZlY3ZSflHwSm5Pt3A28FlufHBwPPDrcQSZ8BTgQ2AG/IzdPzew5Yk9tatY86DhQzq4uyPZQVwBvz/S8BJ0v6z3zk/FnAxcMtJCJOi4i9gEuARbm52cBRDNK+A0kLJa2StGrdunXDLa8091DMrG7KBsrHSXMXRMQ/AceRJuMfJ4XAqRXUdGl+XUg9j70Ky2YAawdp30FEnB8RcyJiztSpUysorz2eQzGzuil7pPzTwNOFx1cCV460CEn7RsTd+eExwB35/lJgkaTLSUNqGyLiIUnLgc8WJuKPBBaPtI4quYdiZnUz3AMb9wP+HJhG6hmsiog723zuZaRdjadIWkPq8RydX3Mb8ABwUl59GWnPstWkIHs3QESsl3QWcENe79MRsd1E/2jhQDGzuih7YOMk0insjyMNlz0FvADYJuk7wPsa9tjaQUQ0O/39hS3WDeDkFsuWAEvar7673EMxs7opO4fyddLw0onALhExCdgFWAC8KS83PIdiZvVTdsjrWOB/R8SlAw0R8SxwiaRdgC9WWVw/cA/FzOqibA/lKeChFsvWkg52NDzkZWb1UzZQzgU+KmnnYmPunXwUD3n9kQPFzOqm7JDXbqTzaj0oaQXwCPBi0vzJM8AqSZ/P60ZEfLyySscYz6GYWd2UDZS/Av6Qb8UzCz9ZWD4gSAdC1pp7KGZWF2UPbJzVqUL6jYe8zKxufAngDnGgmFndlAoUScdJem/h8ax8csgnJF0haffqSzQzs7GgbA/lE8CkwuNzSKez/wfgINLFtwz3UMysfspOyu8D3AogaTfSUfNvj4gfSvotKVianiqlbhwoZlY3w5lDGfiIfD2wFfj3/HgN0L3zw49yDhQzq5uygXIzcIKkXYH3AddExKa8bG/ScSlmZlZDZYe8/g/wfdLJIJ9i+2vIvw24vqK6xjz3UMysbsoeh3KtpL2BVwD3RMQThcVLSNctMRwoZlY/pS+wFRFPAjcq2RN4JCK2RMSy6ssbuxwoZlY3pSflJR0t6XrgWeC3wAG5/XxJ76q4PjMzGyPKHth4Iuk673cACxuefzfw3mbPqyP3UMysbsr2UE4Dzo6IBcA/Nyy7HZhdSVV9wIFiZnVTNlBeBqxosexZtj+K3szMaqRsoDwIvKbFsjl4L68/cg/FzOqmbKBcCJyRJ98HrtooSUcAHwMuqLK4scyBYmZ1U3a34c8BewHfIp12BeA/gfHANyPiqxXWNqY5UMysbsoe2BjAyZK+CBxBOtPweuDHEXFXB+ozM7MxolSgSHpRRDwWEfcA9zRZ/qqIuLWy6sYw91DMrG7KzqH8ez5t/Q4kHQz8ZMQV9QkHipnVTdlAeRpYLukFxUZJh5N2J15aUV19w4FiZnVRNlCOIk3AL5O0M4CktwBXARdHxLsrrm/MGuihmJnVRalAiYiNwJuB3YDvS1oAXAl8OSIWdaC+MctDXmZWN6VPDhkR60l7eE0jnbL+jIhYXHVhY50DxczqZsi9vCR9u8Wix4DHgdcU1omI+J9VFdcP7rkHJk8efJ1ddoGXv7w79ZiZdUo7uw23uk78VuDWQZbX2q67pq/veU976197LRx2WOfqMTPrtCEDJSLe0I1C+s3cubB8OTz55ODr3XsvfOxj8Oij3anLzKxTSl+x0dozbhwceeTQ6918cwqUrVuHXtfMbDQrHSiSXggcS7qu/MTG5RHxsQrqqo3x49PXbdt6W4eZ2UiVPfXKy4GfAbsAuwLrgD3y6zwObCCddbjV85cAbyVdh/6Vue1s4C+BzaTTubw7Ip6QNBP4DXBnfvp1EXFSfs6fAReRzni8DDgln2dszBmX97NzD8XMxrqyuw1/CVgFvAQQcDTpQ/1dwFPAUHt4XQTMa2hbAbwyIg4A7gKKuyDfExEH5ttJhfZvkC5BvG++Nb7mmDHQQ3GgmNlYVzZQ5gLnAZvy4+dHxNaIuBT4AvCVwZ4cEStJZycutl0dEVvyw+uAGYO9hqRpwKSI+HnulVwMvK3k9zFqOFDMrF+UDZSJwMaI2EYKhj0Ly24DXj3Cet5DOo3LgFmSfiXpp5Jem9umA2sK66zJbWOSA8XM+kXZQLmLdF15gF8BJ0maKOl5wHuBtcMtRNJpwBbgktz0ELB3RLwG+FvgUkmTSENtjVrOn0haKGmVpFXr1q0bbnkd40Axs35RNlAuBw7M9z8JHAxsBJ4kzZ98ajhF5HOCvRU4YWByPSI2RcRj+f6NpAn7V5B6JMVhsRkMEmQRcX5EzImIOVOnjr5jMB0oZtYvyl6x8YuF+9dJeiVpQnxn0lUbbytbgKR5wMeB10fE04X2qcD6iNgqaR/S5Pu9EbFe0pOSDgGuB04Ezin7vqOFA8XM+sWwDmyUtB9p3mIi8LvcvLekvSNi2SDPuww4HJgiaQ1wBmmvrp2AFUpnVBzYPfh1wKclbSGd5uWkfGJKgA/y3G7DV7H9vMuY4kAxs35R9jiUVwGXAX9K67mM8a2eHxHzmzRf2GLdK4ArWixbBbxyqHrHgoFAeeop2LCht7VUQYJJk3pdhZn1QtkeyhLgD6T5jtWkgxFtBHbaKX1dvDjd+sFZZ8EnPtHrKsys28oGyp8Cx0XE8k4UU0e77gpXXAEPPNDrSqrxqU/Bfff1ugoz64WygfILYO9OFFJn73hHryuozpe/7Pkgs7oqGygLgcskPQ1cAzzRuEJxTy2rn/HjHShmdVU2UB4F7ied7qSVlpPy1v8cKGb1VTZQ/hk4FPi/eFLemhg3zqfiN6ursoHyBuD9+WSQZjtwD8WsvsqeeuV+wHMk1pIDxay+ygbK3wGn5Ytfme3AgWJWX2WHvD5F2m34Lkn303wvr7kV1GVjlAPFrL7KBspt+WbWlCflzeqr7NmG392pQqw/uIdiVl9l51DMBuVAMauvYZ2+3qyV8eNh0yZ4omF2bdKkNBxmZv3Lf+JWqYkT4dprYfLk7W/zm124wMz6insoVqmzz4Zrrtm+7Zvf7J+zKZtZaw4Uq9SrX51uRcuXw/r1zdc3s/7hIS/rOAkiel2FmXWaA8W6woFi1v8cKNZxUq8rMLNucKBYx3nIy6weHCjWFQ4Us/7nQLGOcw/FrB4cKNZxnkMxqwcHinWceyhm9eBAsa5woJj1PweKdZyHvMzqwYFiHechL7N6cKBYVzhQzPqfA8U6zj0Us3pwoFjHeQ7FrB4cKNZx7qGY1YMDxbrCgWLW/xwo1nHuoZjVgwPFOs5zKGb10NVAkbRE0iOSbiu0nS3pDkm3SLpS0u6FZYslrZZ0p6Q3F9rn5bbVkk7t5vdgw+Meiln/63YP5SJgXkPbCuCVEXEAcBewGEDSbOB4YP/8nK9LGi9pPHAucBQwG5if17VRykNeZvXQ1UCJiJXA+oa2qyNiS354HTAj3z8WuDwiNkXEfcBqYG6+rY6IeyNiM3B5XtdGKQeKWT2MtjmU9wBX5fvTgQcLy9bktlbtTUlaKGmVpFXr1q2ruFxrh+dQzOph1ASKpNOALcAlA01NVotB2puKiPMjYk5EzJk6derIC7VhcQ/FrP9N6HUBAJIWAG8Fjoj440fPGmCvwmozgLX5fqt2G4U85GVWDz3voUiaB3wcOCYini4sWgocL2knSbOAfYFfADcA+0qaJen5pIn7pd2u29rnIS+zeuhqD0XSZcDhwBRJa4AzSHt17QSsUPrkuS4iToqI2yV9G/g1aSjs5IjYml9nEbAcGA8siYjbu/l9WHnuoZj1v64GSkTMb9J84SDrfwb4TJP2ZcCyCkuzDvKQl1k99HzIy/qfA8WsHhwo1nGeQzGrBweKdYV7KGb9z4FiHechL7N6cKBYxzlQzOrBgWJmZpVwoFjHuYdiVg8OFOs4B4pZPThQzMysEg4U6zj3UMzqwYFiHedAMasHB4p1nAPFrB4cKGZmVgkHinWceyhm9eBAsY5zoJjVgwPFusKBYtb/HCjWcT59vVk9OFCs4zzkZVYPDhTrOAeKWT04UMzMrBIOFOs491DM6sGBYh3nQDGrBweKdYUDxaz/OVCs47zbsFk9TOh1Adb/JHjiCdh//15XYlZPL3oRrFzZ+fdxoFjHzZ8Pv/+9h73MemX33bvzPg4U67hDD003M+tvnkMxM7NKOFDMzKwSDhQzM6uEA8XMzCrhQDEzs0o4UMzMrBIOFDMzq4QDxczMKqGo0eHLktYBDwzz6VOARysspyquqxzXVY7rKqcf63pZRExtZ8VaBcpISFoVEXN6XUcj11WO6yrHdZVT97o85GVmZpVwoJiZWSUcKO07v9cFtOC6ynFd5biucmpdl+dQzMysEu6hmJlZJRwoQ5A0T9KdklZLOrXL772XpGsk/UbS7ZJOye1nSvqdpJvy7ejCcxbnWu+U9OYO1na/pFvz+6/KbXtIWiHp7vx1cm6XpK/mum6RdFCHatqvsE1ukrRR0od7tb0kLZH0iKTbCm2lt5GkBXn9uyUt6FBdZ0u6I7/3lZJ2z+0zJT1T2HbnFZ7zZ/l3YHWufUQXe25RV+mfXdV/sy3q+pdCTfdLuim3d2V7DfLZ0Nvfr4jwrcUNGA/cA+wDPB+4GZjdxfefBhyU778QuAuYDZwJfLTJ+rNzjTsBs3Lt4ztU2/3AlIa2zwOn5vunAp/L948GrgIEHAJc36Wf3e+Bl/VqewGvAw4CbhvuNgL2AO7NXyfn+5M7UNeRwIR8/3OFumYW12t4nV8Ah+aarwKO6kBdpX52nfibbVZXw/IvAKd3c3sN8tnQ098v91AGNxdYHRH3RsRm4HLg2G69eUQ8FBG/zPefBH4DTB/kKccCl0fEpoi4D1hN+h665VjgW/n+t4C3FdovjuQ6YHdJ0zpcyxHAPREx2IGsHd1eEbESWN/kPctsozcDKyJifUQ8DqwA5lVdV0RcHRFb8sPrgBmDvUaubVJE/DzSJ9PFhe+lsroG0epnV/nf7GB15V7GXwOXDfYaVW+vQT4bevr75UAZ3HTgwcLjNQz+gd4xkmYCrwGuz02Lctd1yUC3lu7WG8DVkm6UtDC3vSQiHoL0Cw+8uAd1DTie7f/Ie729BpTdRr2o8T2k/2YHzJL0K0k/lfTa3DY919KNusr87Lq9vV4LPBwRdxfaurq9Gj4bevr75UAZXLMxzq7vFifpBcAVwIcjYiPwDeDlwIHAQ6QuN3S33sMi4iDgKOBkSa8bZN2ubkdJzweOAf41N42G7TWUVrV0e9udBmwBLslNDwF7R8RrgL8FLpU0qYt1lf3ZdftnOp/t/3Hp6vZq8tnQctUW719pXQ6Uwa0B9io8ngGs7WYBkp5H+oW5JCK+AxARD0fE1ojYBlzAc8M0Xas3Itbmr48AV+YaHh4YyspfH+l2XdlRwC8j4uFcY8+3V0HZbdS1GvOE7FuBE/KwDHlI6bF8/0bS/MQrcl3FYbGO1DWMn103t9cE4B3AvxTq7dr2avbZQI9/vxwog7sB2FfSrPxf7/HA0m69eR6fvRD4TUR8sdBenH94OzCw98lS4HhJO0maBexLmgisuq5dJb1w4D5pQve2/P4De4ksAL5XqOvEvKfJIcCGgW55h2z3X2Ovt1eDsttoOXCkpMl5uOfI3FYpSfOAjwPHRMTThfapksbn+/uQttG9ubYnJR2Sf09PLHwvVdZV9mfXzb/ZNwJ3RMQfh7K6tb1afTbQ69+v4c7m1+VG2jviLtJ/Gqd1+b3/gtT9vAW4Kd+OBv4JuDW3LwWmFZ5zWq71Tka4180gde1D2nvmZuD2ge0CvAj4EXB3/rpHbhdwbq7rVmBOB7fZLsBjwG6Ftp5sL1KoPQT8gfSf4HuHs41Icxqr8+3dHaprNWksfeD37Ly87nH5Z3wz8EvgLwuvM4f0AX8P8DXygdIV11X6Z1f132yzunL7RcBJDet2ZXvR+rOhp79fPlLezMwq4SEvMzOrhAPFzMwq4UAxM7NKOFDMzKwSDhQzM6uEA8VsjJI0V9KZTdrPlPRoD0qymvNuw2ZjlKRFwDkRoYb2GaRzOt3Ym8qsrib0ugAze46knSPimZG8RqQjt9cMuaJZxTzkZbUiaZGkByX9l6TvSjpCUkg6PC8fJ+nUfCGiTZLuarzokKSfSPo3Se/M622UdFXuGRTXmyjp8/n9Nkm6WYULROV17pf0BUmflLQG2JjbD5W0VNLaXOtNkk4oPO9/Aefk+5FvP8mPdxjyyqci+W6u9UlJ35f0Jw3rhKRTJH1W0jqli0qdK2mnEW10qw33UKw2JL2d9CH8ddI5jv6CdD6konNI50D6NOnUGW8Clkh6LCJ+UFjvYGBP4CPAzsBXgPNJp78Y8G+kkxmeQTrlxV8DSyXNiYibCuu9k3S6jr/hub/JlwE/A84DngUOA/6fpG0RcRnwQ9KZdz9CumgT5DBq8n3vRDoNxx+A95POJvwp4KeSXhURxWt9fAT4MfAu4ADg74EHSBduMhtclecu8s230XwjnTjwhw1tXyedE+lw4E+AbcCChnUuBm4oPP4JsIHCle2AD+fX2Tk/PiI/fn3Da60E/rXw+H7SeaImDlK3SEHzTeDHhfZF6U94h/XPBB4tPD6JFCL7FNpmAJuBxYW2AFY2vNZ3get6/bPzbWzcPORltZDPAHsgO555tvj4CFKgXClpwsCN9N/9gQNnkc1uiHSFuwG/zl8HLk70RtIliH/W5LXmNNTwo4h4tqHeyUrXAH+A1LP4A7CQdCr0suaSTud/70BDpHmWn5F6aUVXNzz+NUNcvdFsgIe8rC6mkn7f1zW0Fx9PIV2TfEOL15jGc5PdTzQs25y/Tiy81ktJQdBoa8Pjh5uscxHp2t9nkT7UNwIfZHiXs53W4j0eJg2tFTX7viZi1gYHitXFOtKwz9SG9uLj9Xmdw0g9lUaPNGlrZT3wO9q7bvh2++5Lmgi8BVgUEecV2oc7ovAQsH+T9pfQ/jXczYbkQLFaiIitkm4i/Yf/zcKiYwr3f0zqoewWEStG+JY/Ik1wPxURd5R87k65jk0DDUoXNDuG7cNnc142sXHIrMH1pIsrzYqI+/JzpgP/nTTfYlYJB4rVyWeB70j6Gmnu5DBSTwBgW0TcKek84HJJnwdWkYZ79gdeERHvK/FeK0hXvlsh6XOkvbgmkeZxJkbE4lZPjIgNkm4ATpe0kdRbOpU0FDepsOpAUJ0i6cfAxoi4s8lLXkS6GuNVkk4nDbmdCTzK9uFqNiKelLfaiIgrgQ+RhqG+C/w58NG8eGCX25NJ8xYnAstIH8ZvIe2dVea9gnS98SWkPcCWkz68DwWubeMl3gncR9rD7Cuka4df3LDOfwBnA6eQeiFNwyEiNpEvV0vaTfpbpF2BD4/tdxk2GxGfesVqTdInSJeS3SNGeIS6Wd15yMtqQ9JUYDFwDfA08FrSUNCFDhOzkXOgWJ1sBv4baThrN9LeT18BPtnLosz6hYe8zMysEp6UNzOzSjhQzMysEg4UMzOrhAPFzMwq4UAxM7NKOFDMzKwS/x99Ws1beCulLwAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "# -*- coding: utf-8 -*-\n",
    "\"\"\"\n",
    "Created on Fri Jul 13 17:24:51 2018\n",
    "\n",
    "Author: cheng-man wu\n",
    "LinkedIn: www.linkedin.com/in/chengmanwu\n",
    "Github: https://github.com/wurmen\n",
    "\n",
    "\"\"\"\n",
    "\n",
    "'''==========Solving job shop scheduling problem by gentic algorithm in python======='''\n",
    "# importing required modules\n",
    "import pandas as pd\n",
    "import numpy as np\n",
    "import time\n",
    "import copy\n",
    "\n",
    "''' ================= initialization setting ======================'''\n",
    "\n",
    "\n",
    "pt_tmp=pd.read_excel(\"JSP_dataset.xlsx\",sheet_name=\"Processing Time\",index_col =[0])\n",
    "ms_tmp=pd.read_excel(\"JSP_dataset.xlsx\",sheet_name=\"Machines Sequence\",index_col =[0])\n",
    "\n",
    "dfshape=pt_tmp.shape\n",
    "num_mc=dfshape[1] # number of machines\n",
    "num_job=dfshape[0] # number of jobs\n",
    "num_gene=num_mc*num_job # number of genes in a chromosome\n",
    "\n",
    "pt=[list(map(int, pt_tmp.iloc[i])) for i in range(num_job)]\n",
    "ms=[list(map(int,ms_tmp.iloc[i])) for i in range(num_job)]\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "# raw_input is used in python 2\n",
    "population_size=int(input('Please input the size of population: ') or 30) # default value is 30\n",
    "crossover_rate=float(input('Please input the size of Crossover Rate: ') or 0.8) # default value is 0.8\n",
    "mutation_rate=float(input('Please input the size of Mutation Rate: ') or 0.2) # default value is 0.2\n",
    "mutation_selection_rate=float(input('Please input the mutation selection rate: ') or 0.2)\n",
    "num_mutation_jobs=round(num_gene*mutation_selection_rate)\n",
    "num_iteration=int(input('Please input number of iteration: ') or 2000) # default value is 2000\n",
    "    \n",
    "start_time = time.time()\n",
    "\n",
    "'''==================== main code ==============================='''\n",
    "'''----- generate initial population -----'''\n",
    "Tbest=999999999999999\n",
    "best_list,best_obj=[],[]\n",
    "population_list=[]\n",
    "makespan_record=[]\n",
    "for i in range(population_size):\n",
    "    nxm_random_num=list(np.random.permutation(num_gene)) # generate a random permutation of 0 to num_job*num_mc-1\n",
    "    population_list.append(nxm_random_num) # add to the population_list\n",
    "    for j in range(num_gene):\n",
    "        population_list[i][j]=population_list[i][j]%num_job # convert to job number format, every job appears m times\n",
    "        \n",
    "for n in range(num_iteration):\n",
    "    Tbest_now=99999999999           \n",
    "   \n",
    "    '''-------- two point crossover --------'''\n",
    "    parent_list=copy.deepcopy(population_list)\n",
    "    offspring_list=copy.deepcopy(population_list)\n",
    "    S=list(np.random.permutation(population_size)) # generate a random sequence to select the parent chromosome to crossover\n",
    "    \n",
    "    for m in range(int(population_size/2)):\n",
    "        crossover_prob=np.random.rand()\n",
    "        if crossover_rate>=crossover_prob:\n",
    "            parent_1= population_list[S[2*m]][:]\n",
    "            parent_2= population_list[S[2*m+1]][:]\n",
    "            child_1=parent_1[:]\n",
    "            child_2=parent_2[:]\n",
    "            cutpoint=list(np.random.choice(num_gene, 2, replace=False))\n",
    "            cutpoint.sort()\n",
    "        \n",
    "            child_1[cutpoint[0]:cutpoint[1]]=parent_2[cutpoint[0]:cutpoint[1]]\n",
    "            child_2[cutpoint[0]:cutpoint[1]]=parent_1[cutpoint[0]:cutpoint[1]]\n",
    "            offspring_list[S[2*m]]=child_1[:]\n",
    "            offspring_list[S[2*m+1]]=child_2[:]\n",
    "        \n",
    "    \n",
    "    '''----------repairment-------------'''\n",
    "    for m in range(population_size):\n",
    "        job_count={}\n",
    "        larger,less=[],[] # 'larger' record jobs appear in the chromosome more than m times, and 'less' records less than m times.\n",
    "        for i in range(num_job):\n",
    "            if i in offspring_list[m]:\n",
    "                count=offspring_list[m].count(i)\n",
    "                pos=offspring_list[m].index(i)\n",
    "                job_count[i]=[count,pos] # store the above two values to the job_count dictionary\n",
    "            else:\n",
    "                count=0\n",
    "                job_count[i]=[count,0]\n",
    "            if count>num_mc:\n",
    "                larger.append(i)\n",
    "            elif count<num_mc:\n",
    "                less.append(i)\n",
    "                \n",
    "        for k in range(len(larger)):\n",
    "            chg_job=larger[k]\n",
    "            while job_count[chg_job][0]>num_mc:\n",
    "                for d in range(len(less)):\n",
    "                    if job_count[less[d]][0]<num_mc:                    \n",
    "                        offspring_list[m][job_count[chg_job][1]]=less[d]\n",
    "                        job_count[chg_job][1]=offspring_list[m].index(chg_job)\n",
    "                        job_count[chg_job][0]=job_count[chg_job][0]-1\n",
    "                        job_count[less[d]][0]=job_count[less[d]][0]+1                    \n",
    "                    if job_count[chg_job][0]==num_mc:\n",
    "                        break     \n",
    "    \n",
    "    '''--------mutatuon--------'''   \n",
    "    for m in range(len(offspring_list)):\n",
    "        mutation_prob=np.random.rand()\n",
    "        if mutation_rate >= mutation_prob:\n",
    "            m_chg=list(np.random.choice(num_gene, num_mutation_jobs, replace=False)) # chooses the position to mutation\n",
    "            t_value_last=offspring_list[m][m_chg[0]] # save the value which is on the first mutation position\n",
    "            for i in range(num_mutation_jobs-1):\n",
    "                offspring_list[m][m_chg[i]]=offspring_list[m][m_chg[i+1]] # displacement\n",
    "            \n",
    "            offspring_list[m][m_chg[num_mutation_jobs-1]]=t_value_last # move the value of the first mutation position to the last mutation position\n",
    "  \n",
    "    \n",
    "    '''--------fitness value(calculate makespan)-------------'''\n",
    "    total_chromosome=copy.deepcopy(parent_list)+copy.deepcopy(offspring_list) # parent and offspring chromosomes combination\n",
    "    chrom_fitness,chrom_fit=[],[]\n",
    "    total_fitness=0\n",
    "    for m in range(population_size*2):\n",
    "        j_keys=[j for j in range(num_job)]\n",
    "        key_count={key:0 for key in j_keys}\n",
    "        j_count={key:0 for key in j_keys}\n",
    "        m_keys=[j+1 for j in range(num_mc)]\n",
    "        m_count={key:0 for key in m_keys}\n",
    "        \n",
    "        for i in total_chromosome[m]:\n",
    "            gen_t=int(pt[i][key_count[i]])\n",
    "            gen_m=int(ms[i][key_count[i]])\n",
    "            j_count[i]=j_count[i]+gen_t\n",
    "            m_count[gen_m]=m_count[gen_m]+gen_t\n",
    "            \n",
    "            if m_count[gen_m]<j_count[i]:\n",
    "                m_count[gen_m]=j_count[i]\n",
    "            elif m_count[gen_m]>j_count[i]:\n",
    "                j_count[i]=m_count[gen_m]\n",
    "            \n",
    "            key_count[i]=key_count[i]+1\n",
    "    \n",
    "        makespan=max(j_count.values())\n",
    "        chrom_fitness.append(1/makespan)\n",
    "        chrom_fit.append(makespan)\n",
    "        total_fitness=total_fitness+chrom_fitness[m]\n",
    "\n",
    "    \n",
    "    '''----------selection(roulette wheel approach)----------'''\n",
    "    pk,qk=[],[]\n",
    "    \n",
    "    for i in range(population_size*2):\n",
    "        pk.append(chrom_fitness[i]/total_fitness)\n",
    "    for i in range(population_size*2):\n",
    "        cumulative=0\n",
    "        for j in range(0,i+1):\n",
    "            cumulative=cumulative+pk[j]\n",
    "        qk.append(cumulative)\n",
    "    \n",
    "    selection_rand=[np.random.rand() for i in range(population_size)]\n",
    "    \n",
    "    for i in range(population_size):\n",
    "        if selection_rand[i]<=qk[0]:\n",
    "            population_list[i]=copy.deepcopy(total_chromosome[0])\n",
    "        else:\n",
    "            for j in range(0,population_size*2-1):\n",
    "                if selection_rand[i]>qk[j] and selection_rand[i]<=qk[j+1]:\n",
    "                    population_list[i]=copy.deepcopy(total_chromosome[j+1])\n",
    "                    break\n",
    "    '''----------comparison----------'''\n",
    "    for i in range(population_size*2):\n",
    "        if chrom_fit[i]<Tbest_now:\n",
    "            Tbest_now=chrom_fit[i]\n",
    "            sequence_now=copy.deepcopy(total_chromosome[i])\n",
    "    if Tbest_now<=Tbest:\n",
    "        Tbest=Tbest_now\n",
    "        sequence_best=copy.deepcopy(sequence_now)\n",
    "        \n",
    "    makespan_record.append(Tbest)\n",
    "'''----------result----------'''\n",
    "print(\"optimal sequence\",sequence_best)\n",
    "print(\"optimal value:%f\"%Tbest)\n",
    "print('the elapsed time:%s'% (time.time() - start_time))\n",
    "\n",
    "import matplotlib.pyplot as plt\n",
    "%matplotlib inline\n",
    "plt.plot([i for i in range(len(makespan_record))],makespan_record,'b')\n",
    "plt.ylabel('makespan',fontsize=15)\n",
    "plt.xlabel('generation',fontsize=15)\n",
    "plt.show()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<iframe id=\"igraph\" scrolling=\"no\" style=\"border:none;\" seamless=\"seamless\" src=\"https://plot.ly/~ftcu5931/6.embed\" height=\"600px\" width=\"900px\"></iframe>"
      ],
      "text/plain": [
       "<plotly.tools.PlotlyDisplay object>"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "'''--------plot gantt chart-------'''\n",
    "import pandas as pd\n",
    "import plotly.plotly as py\n",
    "import plotly.figure_factory as ff\n",
    "import datetime\n",
    "\n",
    "m_keys=[j+1 for j in range(num_mc)]\n",
    "j_keys=[j for j in range(num_job)]\n",
    "key_count={key:0 for key in j_keys}\n",
    "j_count={key:0 for key in j_keys}\n",
    "m_count={key:0 for key in m_keys}\n",
    "j_record={}\n",
    "for i in sequence_best:\n",
    "    gen_t=int(pt[i][key_count[i]])\n",
    "    gen_m=int(ms[i][key_count[i]])\n",
    "    j_count[i]=j_count[i]+gen_t\n",
    "    m_count[gen_m]=m_count[gen_m]+gen_t\n",
    "    \n",
    "    if m_count[gen_m]<j_count[i]:\n",
    "        m_count[gen_m]=j_count[i]\n",
    "    elif m_count[gen_m]>j_count[i]:\n",
    "        j_count[i]=m_count[gen_m]\n",
    "    \n",
    "    start_time=str(datetime.timedelta(seconds=j_count[i]-pt[i][key_count[i]])) # convert seconds to hours, minutes and seconds\n",
    "    end_time=str(datetime.timedelta(seconds=j_count[i]))\n",
    "        \n",
    "    j_record[(i,gen_m)]=[start_time,end_time]\n",
    "    \n",
    "    key_count[i]=key_count[i]+1\n",
    "        \n",
    "\n",
    "df=[]\n",
    "for m in m_keys:\n",
    "    for j in j_keys:\n",
    "        df.append(dict(Task='Machine %s'%(m), Start='2018-07-14 %s'%(str(j_record[(j,m)][0])), Finish='2018-07-14 %s'%(str(j_record[(j,m)][1])),Resource='Job %s'%(j+1)))\n",
    "    \n",
    "fig = ff.create_gantt(df, index_col='Resource', show_colorbar=True, group_tasks=True, showgrid_x=True, title='Job shop Schedule')\n",
    "py.iplot(fig, filename='GA_job_shop_scheduling', world_readable=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
